#include<iostream>
#include<vector>
#include<random>
using namespace std;
template<typename T>
struct node {//索引双向链表结点
    T value;
    node<T>* next;
    node<T>* prev;
    node<T>* down;
    node(T val) {
        value = val;
        next = NULL;
        prev = NULL;
        down = NULL;
    }
    node() {
        next = NULL;
        prev = NULL;
        down = NULL;
    }
};
template<typename T>
struct  lst {
    struct node<T>* List;
    int size;
    lst() {
        size = 0;
        List = NULL;
    }
};
template<typename T>
class skip_list {
private:
    int random_num() {
       std::random_device rd;         // 随机数种子
       std::mt19937 gen(rd());        // Mersenne Twister引擎
       std::uniform_int_distribution<int> dis(0, lever - 1); // 均匀分布
        return dis(gen); // 生成0到max_level-1的整数
    }
private:
    int size;
    int lever;
    std::vector<lst<T>*> list;//0层表示原始数据结点
public:
    //析构函数
    ~skip_list(){
        clear();
        for(int i=0;i<list.size();i++){
            delete list[i];
        }
        cout<<"~skip_list"<<endl;
    }
    //无参构造
    skip_list() {
        size = 0;
        lever = 2;
        lst<T>* val_list = new lst<T>();
        lst<T>* idx = new lst<T>();
        list.push_back(val_list);
        list.push_back(idx);
    }

    //指定索引层数
    skip_list(int lever) {
        size = 0;
        this->lever = lever;
        lst<T>* val_list;
        val_list = new lst<T>;
        list.push_back(val_list);
        for (int i = 1; i < lever; i++) {
            lst<T>* idx;
            idx = new lst<T>;
            list.push_back(idx);
        }
    }

    //返回跳表总容量
    int Size() {
        return size;
    }

    //返回跳表总层数
    int Lever() {
        return lever;
    }

    //查找结点
    node<T>* get(T val,int& level) {
        node<T>* low = list[lever - 1]->List;//双指针遍历找到最后一个小于val的结点
        node<T>* high = list[lever - 1]->List;
        for (int i = lever - 1; i >= 0; i--) {
            if (high == NULL && low == NULL) {//说明顶层索引为空,跳至下一层索引
                low = list[i - 1]->List;
                high = list[i - 1]->List;
                continue;
            }
            else high = high->next; //非空则调整high结点后移
            while (high != NULL && high->value <= val) {
                high = high->next;
                low = low->next;
            }
            if (low->value == val) {
                level = i;
                return low;
            }
            else {
                low = low->down;
                high = low;
            }
        }
        return NULL;
    }

    //删除结点
    bool delt(T val) {
        int level = 0;
        node<T>* high = get(val,level);
        if (high == NULL) return false;
        size--;
        node<T>* low = high;
        low = high->down;
        if (low == NULL) {
            if (list[level]->size == 1) {
                list[level]->List = NULL;
            }
            else
                {   
                    if(high->prev==NULL){
                        list[level]->List=high->next;
                        if(high->next!=NULL){
                            high->next->prev=NULL;
                        }
                    }
                    else if (high->next == NULL) {
                        high->prev->next = NULL;
                    }
                    else
                    {
                        high->next->prev = high->prev;
                        high->prev->next = high->next;
                    }
                }
            delete(high);
            list[level]->size--;
        }
        else {
            while (low != NULL) {
                if (list[level]->size == 1) {
                    list[level]->List = NULL;
                }
                else
                {   
                    if(high->prev==NULL){
                        list[level]->List=high->next;
                        if(high->next!=NULL){
                            high->next->prev=NULL;
                        }
                    }
                    else if (high->next == NULL) {
                        high->prev->next = NULL;
                    }
                    else
                    {
                        high->next->prev = high->prev;
                        high->prev->next = high->next;
                    }
                }
                delete(high);
                high = low;
                low = low->down;
                list[level]->size--;
                level--;
            }
            if (list[level]->size == 1) {
                list[level]->List = NULL;
            }
            else
                {   
                    if(high->prev==NULL){
                        list[level]->List=high->next;
                        if(high->next!=NULL){
                            high->next->prev=NULL;
                        }
                    }
                    else if (high->next == NULL) {
                        high->prev->next = NULL;
                    }
                    else
                    {
                        high->next->prev = high->prev;
                        high->prev->next = high->next;
                    }
                }
            delete(high);
            list[level]->size--;
        }
        return true;
    }

    //清空结点
    bool clear(){
        for(int i=lever-1;i>=0;i--){
            while(list[i]->size!=0){
                node<T> *idx=list[i]->List;
                if(idx!=NULL){
                    delt(idx->value);
                }
            }
        }
        return true;
    }

    //插入结点
    bool insert(T val) {
        size++;
        node<T>* index;//遍历指针
        if (list[lever - 1]->size >= 100) {//如果最高索引的数目大于100，则升级索引层数
            lst<T>* idx = new lst<T>;
            list.push_back(idx);
            node<T>* high;//新最高索引的遍历指针
            index = list[lever - 1]->List;
            node<T>* n = new node<T>(index->value);
            idx->List = n;
            high = idx->List;
            high->down = index;
            idx->size++;
            for (int i = 0; i < list[lever - 1]->size / 10; i++) {
                for (int i = 0; i < 10; i++) {
                    index = index->next;
                }
                if(index!=NULL)
                {
                    n = new node<T>(index->value);
                    high->next = n;
                    n->prev = high;
                    n->down = index;
                    high = high->next;
                    idx->size++;
                }
            }
            lever++;
        }
        int temp_lever = random_num();//获取随机插入层级
        node<T>* p = new node<T>(val);
        for (int i = temp_lever; i >= 0; i--) {
            index = list[i]->List;
            list[i]->size++;
            if (index == NULL) {//如果为空表，直接插入
                list[i]->List = p;
                p->next = NULL;
            }
            else {
                while (index->next != NULL && index->value < val) {//找到插入位置
                    index = index->next;
                }
                if (index->next == NULL) {//插入
                    index->next = p;
                    p->prev = index;
                    p->next = NULL;
                }
                else {
                    p->next = index;
                    p->prev = index->prev;
                    index->prev = p;
                    p->prev->next = p;
                }
            }
            p->down = new node<T>(val);
            p = p->down;
        }
        delete(p);
        p = list[0]->List;
        while (p != NULL) {
            p->down = NULL;
            p = p->next;
        }
        return true;
    }
    void myprint() {
        node<T>* p;
        for (int i = 0; i < lever; i++) {
            cout << "第" << i << "层：";
            p = list[i]->List;
            while (p != NULL) {
                cout << p->value << "->";
                p = p->next;
            }
            cout << "NULL" << endl;
        }
    }
};